import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 困难
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 思路：
 * 对于每个柱子为高度的矩形，宽是其右边第一个比他矮的柱子索引 - 其左边第一个比他矮的柱子索引
 * @since 2023-09-12 9:02
 */
public class _084柱状图中最大的矩形 {
    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println(new _084柱状图中最大的矩形().largestRectangleArea(heights));
    }

    //单挑栈
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        int index, left;
        //使用栈维系递增的柱状索引
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < heights.length; i++) {
            //当前柱子高度小于栈顶，以栈顶为高的矩形找到了
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                index = stack.pop();
                if (stack.isEmpty()) {
                    left = -1;
                } else {
                    left = stack.peek();
                }
                res = Math.max(res, heights[index] * (i - left - 1));
            }
            stack.push(i);
        }
        //剩下的柱子右边没有更矮的柱子
        int right = heights.length;
        while (!stack.isEmpty()) {
            index = stack.pop();
            if (stack.isEmpty()) {
                left = -1;
            } else {
                left = stack.peek();
            }
            res = Math.max(res, heights[index] * (right - left - 1));
        }
        return res;
    }
}
